#include<iostream>
#include<algorithm>
#include<assert.h>
#include<stack>
#include<vector>
#include<string>
using namespace std;

namespace Mylist
{
    //节点类封装
    template<class T>
    struct list_node
    {
        //成员变量，前节点指针，后节点指针，存储的数据val
        list_node<T>* _next;
        list_node<T>* _prev;
        T _val;

        //构造函数  创造节点
        list_node(const T& val=T())
        :_next(nullptr)
        ,_prev(nullptr)
        ,_val(val)
        {}
    };

    //迭代器类封装
    template<class T,class Ref,class Ptr>
    struct _list_iterator
    { 
        typedef _list_iterator<T,Ref,Ptr> self;
        typedef list_node<T> node;
        //成员变量 一个节点的指针
        node* _node;

        //构造函数 将传入的节点指针变为迭代器
        _list_iterator(node* node)
        :_node(node)
        {}

        Ref operator*(){
            return _node->_val;
        }

        Ptr operator->(){
            return &_node->_val;
        }

        bool operator!=(const self& it){
            return _node!=it._node;
        }

        self& operator++(){
            _node=_node->_next;
            return *this;
        }

        self operator++(int){
            self tmp(*this);
            _node=_node->_next;
            return tmp;
        }

        self& operator--(){
            _node=_node->_prev;
            return *this;
        }

        self operator--(int){
            self tmp(*this);
            _node=_node->_prev;
            return tmp;
        }


    };

    //链表类封装
    template<class T>
    class list
    {
        typedef list_node<T> node;

        void empty_init(){
             _head=new node;
            _head->_next=_head;
            _head->_prev=_head;
            _size=0;
        }
    public:
        //重定义迭代器类型
        typedef _list_iterator<T,T&,T*> iterator;
        typedef _list_iterator<T,const T&,const T*> const_iterator; 
        iterator begin(){
            //隐式类型转换，相当于调用_list_iterator()构造函数，创建迭代器类型的对象返回
            return _head->_next;          
        }
        iterator end(){
            return _head;
        }
        const_iterator begin()const {
            return _head->_next;
        }
        const_iterator end()const {
            return _head;
        }

        
        //构造函数 创建带哨兵节点的链表
        list(){
            cout<<"list()"<<endl;
            empty_init();
        }
        //拷贝构造函数
        list(const list<T>& lt){
            empty_init();
            for(auto& e:lt){
                push_back(e);
            }
        }
        void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}
        //赋值运算符重载
        list<T>& operator=(list<T> lt){
            swap(lt);
            return *this;
        }

        void clear(){
            auto it=begin();
            while(it!=end()){
            it=erase(it);
            }
            _size=0;
        }
        //析构函数
        ~list(){
            cout<<"~list()"<<endl;
            clear();
            delete _head;
            _head=nullptr;
        }

        //插入
        iterator insert(iterator pos ,const T& x){
            node* cur=pos._node;
            node* prev=cur->_prev;
            node* newnode=new node(x);

            prev->_next=newnode;
            newnode->_prev=prev;
            newnode->_next=cur;
            cur->_prev=newnode;
            _size++;
            return pos;
        }
        //尾插
        void push_back(const T& x){
           /* node* newnode=new node(x);
            node*prev=_head->_prev;
            prev->_next=newnode;
            newnode->_next=_head;
            newnode->_prev=prev;
            _head->_prev=newnode;
            _size++;*/
            insert(end(),x);
        }
        //头插
        void push_front(const T& x){
            insert(begin(),x);
        }

        //删除
        iterator erase(iterator pos){
            assert(pos!=end());
            node* cur=pos._node;
            node* prev=cur->_prev;
            node* next=cur->_next;

            prev->_next=next;
            next->_prev=prev;
            _size--;
            return next;
        }
        //尾删
        void pop_back(){
            //这里end()要先减后用，所以有前置--
            erase(--end());
        }
        //头删
        void pop_front(){
            erase(begin());
        }

        size_t size()const {
            return _size;
        }

    private:
        //成员变量 哨兵节点
        node* _head;
        size_t _size;

    };

    //测试用例类
    class A{
        public:
        A(int a1=0,int a2=0)
        :_a1(a1)
        ,_a2(a2)
        {}
        int _a1;
        int _a2;
    };
}
